package TOP101;

/**
 * @Question BM4
 * @Date 2022/11/2 8:59
 * @Solution
 */
public class BM4 {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null && list2 != null) {
            return list2;
        } else if (list1 != null && list2 == null) {
            return list1;
        } else if (list1 == null && list2 == null) {
            return null;
        }
        if (list1.val < list2.val) {
            ListNode temp = list1;
            list1 = list2;
            list2 = temp;
        }

        ListNode insertCur = list2;
        ListNode cur = list1;
        while (insertCur != null) {
            while (cur != null) {
                if (insertCur == list2 && list1.val >= list2.val) {
                    ListNode t = new ListNode(list2.val);
                    t.next = list1;
                    list1 = t;
                    cur = list1;
                    break;
                }
                if (cur.next == null) {
                    cur.next = new ListNode(insertCur.val);
                    break;
                }
                if (insertCur.val <= cur.next.val) {
                    ListNode node = new ListNode(insertCur.val);
                    node.next = cur.next;
                    cur.next = node;
                    cur = list1;
                    break;
                }
                cur = cur.next;
            }
            insertCur = insertCur.next;
        }
        return list1;
    }
}
